package 左哥算法.ch10暴力递归;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Ch02暴力递归与动态规划 {
    @Test
    public void test01() {
        System.out.println(f1(7));
        System.out.println(f2(7));
        System.out.println(f3(7));
    }

    /**
     * 求斐波那契数列的第N项
     */
    public int f1(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return f1(n - 1) + f1(n - 2);
    }

    /**
     * 递归的改进方式,将过程保存起来
     */
    Map<Integer, Integer> map = new HashMap<>();

    public int f2(int n) {
        if (map.containsKey(n)) {
            return n;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int res = f2(n - 1) + f1(n - 2);
        map.put(n, res);
        return res;
    }

    /**
     * 动态规划模式，动态规划是将每一个结果放入到数组中，调用函数就相当于去结果中去数据
     * 什么情况适合改动态规划？可变参数一旦固定，结果一定一样的情况适合转动态规划。（称为无后效性的情况    ）
     */
    public int f3(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * ch02：给你一个数N，表示有多少个位置。（2<=N）
     * start，end，分别表示你的起始位置，以及你要到达的终点。
     * 求当你只能走K步时，从start走到end有多少种方法
     * <p>
     * 思路：
     * 设结果为f(n,s,e,k)
     * 当k<(end-start)时，有0种走法，f(n,s,e,k)=0
     * 当k==(end-start)时，有1种走法，f(n,s,e,k)=1
     * 当k>(end-start)时，f(n,s,e,k)=f(n,s+1,e,k-1)+f(n,s-1,e,k-1)。（这里的s+1和s-1都要在N的范围内）
     */
    @Test
    public void walWaysTest() {
        System.out.println(walWays(10, 2, 4, 4));
        System.out.println(dpWal(10, 2, 4, 4));
        contrastWalWays();
    }

    public void contrastWalWays(){
        int count=10000;
        while (count-- > 0) {
            int n= (int) (Math.random()*20+2);
            int s= (int) (Math.random()*n+1);
            int e= (int) (Math.random()*n+1);
            int k= (int) (Math.random()*20+1);
            if (walWays(n,s,e,k)!=dpWal(n,s,e,k)){
                System.out.println("存在错误：");
                System.out.println(n);
                System.out.println(s);
                System.out.println(e);
                System.out.println(k);
            }
        }
    }

    public int walWays(int n, int s, int e, int k) {
        if (k < Math.abs(e - s)) {
            return 0;
        }
        if (k == Math.abs(e - s)) {
            return 1;
        }
        if (1 == s || n == s) {    //抵达边界
            return walWays(n, s == 1 ? s + 1 : n - 1, e, k - 1);
        }
        return walWays(n, s - 1, e, k - 1) + walWays(n, s + 1, e, k - 1);
    }

    public int dpWal(int n, int s, int e, int k) {
        int[][] dp = new int[k + 1][n + 1];
        //basecase
        dp[0][e]=1;

        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                if (j!=n){
                    dp[i][j]+=dp[i-1][j+1];
                }
                if (j!=1){
                    dp[i][j]+=dp[i-1][j-1];
                }
            }
        }

        return dp[k][s];
    }

    /**
     * ch03：找零钱
     */
    @Test
    public void coinChangeTest() {
        int n1 = minCoin1(new int[]{1,2,5}, 11);
        System.out.println(n1);
        int n2 = minCoin2(new int[]{2,7,3,5,3}, 4,10);
        System.out.println(n2);
        int n3 = dpMinCoin(new int[]{2,7,3,5,3}, 10);
        System.out.println(n3);
        compareCoin();
    }

    /**
     * ch03：找零钱问题
     * 给你一个数组coins，数组中放着某个面值的硬币。（硬币面值可能重复）
     * 计算总金额为n时，所需要的最少硬币。
     * <p>
     * 递归思路1：
     * f(n)=Min( f(n-coins[0])(去掉0号) , f(n-coins[1])(去掉1号)...)+1。
     * 这种方式有后效性，f(coins，amount)需要判断父问题是否选择某一硬币。
     * 无法转化为动态规划
     */
    public int minCoin1(int[] coins, int amount) {
        if (amount <= 0) {
            return 0;
        }
        int[] select = new int[coins.length];
        for (int i = 0; i < coins.length; i++) {
            int currCoins = coins[i];
            if (currCoins == 0 || currCoins > amount) {  //该枚硬币被取走（被父问题取走），或无法选择该枚硬币时
                select[i] = -1;
                continue;
            }
            coins[i] = 0;     //取走该枚硬币
            select[i] = minCoin1(coins, amount - currCoins);
            coins[i] = currCoins;
        }
        int min = min(select);
        return min != -1 ? min + 1 : min;   //min+1加上刚刚取走的硬币
    }

    private int min(int[] select) {
        int min = -1;
        for (int s : select) {
            if (min == -1) {
                min = s;
            } else {
                min = s == -1 ? min : Math.min(min, s);
            }
        }
        return min;
    }
    /**
     * ch03-2：
     * 找硬币无后效性解法
     * 设结果为f(c,i,n)，c代表硬币，i代表有几枚硬币，n代表总金额。f(c,i,n)表示当有i枚，能凑成n的最少硬币
     *  思路：
     *      f(c,i,n)=min（选择该硬币，不选择该硬币）。即：min(f(c,i+1,n-c[i])+1 ， f(c,i+1,n))
     *      这种方式没有后效性，因为子问题不需要判断某一枚是否被父问题选择（无论是否选择子问题都不能选）
     */
    public int minCoin2(int[]coins,int index,int amount){
        if (amount<0){
            return -1;
        }
        if (amount==0){
            return 0;
        }
        if (index<0){
            return -1;
        }
        int selectCurr = minCoin2(coins, index - 1, amount - coins[index]);
        int noSelectCurr = minCoin2(coins, index - 1, amount);
        if (selectCurr==-1){
            return noSelectCurr;
        }
        selectCurr+=1;
        if (noSelectCurr==-1){
            return selectCurr;
        }
        return Math.min(selectCurr,noSelectCurr);
    }

    public int dpMinCoin(int[] coins,int amount){
        int[][] dp=new int[coins.length+1][amount+1];
        for (int[] d : dp) {
            for (int i = 1; i < d.length; i++) {
                d[i]=-1;
            }
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j <= amount; j++) {
                int selectCurr=j<coins[i-1]?-1:dp[i-1][j-coins[i-1]];
                int noSelect=dp[i-1][j];
                if (selectCurr==-1&&noSelect==-1){
                    dp[i][j]=-1;
                }else {
                    if (selectCurr==-1){
                        dp[i][j]=noSelect;
                    }else if (noSelect==-1){
                        dp[i][j]=selectCurr+1;
                    }else {
                        dp[i][j]=Math.min(selectCurr+1,noSelect);
                    }
                }
            }
        }
        return dp[coins.length][amount];
    }
    //找硬币比较器
    public void compareCoin(){
        int count=10000;
        while (count-- > 0) {
            int amount= (int) (Math.random()*100+1);
            int[] coins=new int[(int) (Math.random()*50+1)];
            for (int i = 0; i < coins.length; i++) {
                coins[i]= (int) (Math.random()*100+1);
            }
            int dpfun = dpMinCoin(coins, amount);
            int fun1 = minCoin1(coins, amount);
            int fun2 = minCoin2(coins, coins.length - 1, amount);
            if (dpfun!= fun1 ||dpfun!= fun2){
                System.out.println("错误");
            }
        }
    }

    @Test
    public void test(){
//        int[] arr={1,4,4};
        int[] arr={7,2,5,10,8};
        int k=2;
        System.out.println(splitArray(arr,k, arr.length));
        System.out.println(splitArray3(arr,k, 0));
        System.out.println(dpFun(arr,k));
    }

    /**
     * 剩余index个容器时，放入count元素个时能拿到最大数组的最小值
     */
    public int splitArray(int[] nums, int k,int count) {
        if (1==k){
            return sum(nums,nums.length-count,nums.length);
        }
        int curr=0;
        int max;
        int min=Integer.MAX_VALUE;
        for (int i = 1; i <= count-k+1; i++) {
            curr=sum(nums,nums.length-count,nums.length-count+i);
            int other = splitArray(nums, k - 1, count - i);
            max=Math.max(curr,other);
            min=Math.min(min,max);
        }
        return min;
    }
    int[][] dp=new int[100][100];
    public int splitArray3(int[] nums, int k,int count) {
        if (dp[k][count]!=0){
            return dp[k][count];
        }
        if (1==k){
            dp[k][count]=sum(nums,count,nums.length);
            return dp[k][count];
        }
        int curr=0;
        int max;
        int min=Integer.MAX_VALUE;
        for (int i =count+1; i<= nums.length-k+1; i++) {
            curr=sum(nums,count,i);
            int other = splitArray3(nums, k - 1, i);
            max=Math.max(curr,other);
            min=Math.min(min,max);
        }
        dp[k][count]=min;
        return dp[k][count];
    }

    public int splitArray2(int[] nums, int k,int count) {
        if (dp[k][count]!=0){
            return dp[k][count];
        }
        if (1==k){
            dp[k][count]=sum(nums,count,nums.length);
            return dp[k][count];
        }
        int curr=0;
        int max;
        int min=Integer.MAX_VALUE;
        for (int i =count+1; i<= nums.length-k+1; i++) {
            curr=sum(nums,count,i);
            int other = splitArray3(nums, k - 1, i);
            max=Math.max(curr,other);
            min=Math.min(min,max);
        }
        dp[k][count]=min;
        return dp[k][count];
    }

    public int dpFun(int[] nums, int k) {
        int[][] dp=new int[k+1][nums.length+1];
        Arrays.fill(dp[0],Integer.MIN_VALUE);
        for (int i = 0; i < dp[k].length; i++) {
            dp[1][i]=sum(nums,nums.length-i,nums.length);
        }
        for (int i = 2; i<=k; i++) {
            for (int j = nums.length-1; j>=0; j--) {
                dp[i][j]=Integer.MAX_VALUE;
                for (int z =j-1; z>i-1; z--) {
                    int r=sum(nums,nums.length-j,nums.length-z);
                    int max=Math.max(r,dp[i-1][z]);
                    dp[i][j]=Math.min(dp[i][j],max);
                }
            }
        }
        return dp[k][0];
    }

    /**
     * 从s位置加到e位置，不包括e
     */
    public int sum(int[] nums,int s,int e){
        int res=0;
        while (s < e) {
            res+=nums[s++];
        }
        return res;
    }
}
